/**
 * 59.螺旋矩阵II
 * 54.螺旋矩阵
 * **/

#include <iostream>
#include <vector>
using namespace std;

template <class T>
void print(const T &t)
{
    class T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    // 59. 给一个正整数n，生成顺时针n*n螺旋矩阵
    vector<vector<int>> generateMatrix(int n)
    {
        // 坚持左闭右开原则
        vector<vector<int>> matrix(n, vector<int>(n, 0));
        int cnt = 1;
        for (int j = 0; j < int(matrix.size() / 2); ++j) {
            // →
            for (int i = j; i < n - j - 1; ++i) {
                matrix[j][i] = cnt++;
            }
            // ↓
            for (int i = j; i < n - j - 1; ++i) {
                matrix[i][n - j - 1] = cnt++;
            }
            // ←
            for (int i = n - j - 1; i > j; --i) {
                matrix[n - j - 1][i] = cnt++;
            }
            // ↑
            for (int i = n - j - 1; i > j; --i) {
                matrix[i][j] = cnt++;
            }
        }
        if (n % 2 != 0) {
            int mid = n / 2;
            matrix[mid][mid] = cnt;
        }
        return matrix;
    }
    // 54. 给一个m*n矩阵，按顺时针打印
    vector<int> spiralOrder(vector<vector<int>> &matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> res(m * n, 0);
        // cout << m << n << endl;
        int pos = 0;
        int left = 0, right = n - 1, up = 0, down = m - 1;
        while (left < right && up < down) {
            for (int i = left; i < right; ++i) {
                res[pos++] = matrix[up][i];
            }
            for (int i = up; i < down; ++i) {
                res[pos++] = matrix[i][right];
            }
            for (int i = right; i > left; --i) {
                res[pos++] = matrix[down][i];
            }
            for (int i = down; i > up; --i) {
                res[pos++] = matrix[i][left];
            }
            ++left, --right, ++up, --down;
        }

        if (left < right && up == down) {
            for (int i = left; i <= right; ++i) {
                res[pos++] = matrix[up][i];
            }
        }
        if (up < down && left == right) {
            for (int i = up; i <= down; ++i) {
                res[pos++] = matrix[i][right];
            }
        }
        if (m == n && n % 2 != 0) {
            int mid = n / 2;
            res[pos] = matrix[mid][mid];
        }

        return res;
    }
};

Solution solve = Solution();

void test59()
{
    vector<vector<int>> nums = solve.generateMatrix(10);
    for (auto &num : nums) {
        print(num);
    }
}
void test54()
{

    vector<vector<int>> matrix = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}};
    print(solve.spiralOrder(matrix));
}
int main()
{
    // test59();
    test54();
    return 0;
}